﻿#include "bpt_inner_node.h"

bool BPTInnerNode::spilled() {
	return size >= branchs;
}

BPTInnerNode* BPTInnerNode::split(unsigned long& ret_min_key) {
	/*
	* ret_min_key: 分裂返回右节点的最小值，作为父节点的key
	*/
	assert(spilled());
	// 溢出，分裂
	size = size / 2;
	BPTInnerNode* new_node = new BPTInnerNode(branchs);
	new_node->size = branchs - size - 1;
	for (int i = size + 1; i < branchs; i++) {
		new_node->keys[i - size - 1] = keys[i];
		new_node->nodes[i - size - 1] = nodes[i];
	}
	new_node->nodes[new_node->size] = nodes[branchs];
	// 取中间的为新节点的下界key，便于父节点插入
	ret_min_key = keys[size];

	return new_node;
}


void BPTInnerNode::print() {
	printf("INode-s%d:", size);
	for (int i = 0; i < size - 1; i++) {
		printf("%ld|", keys[i]);
	}
	printf("%ld", keys[size - 1]);
}

BPTInnerNode::BPTInnerNode(int b) :
	branchs(b)
{
	// 多分配一个，便于满时直接分裂
	keys = new unsigned long[b];
	nodes = new BPTNode * [b + 1];
}

BPTInnerNode::~BPTInnerNode() {
	delete [] keys;
	delete [] nodes;
}

void BPTInnerNode::insert_first(unsigned long key, BPTNode* left, BPTNode* right) {
	size++;
	keys[0] = key;
	nodes[0] = left;
	nodes[1] = right;
}

void BPTInnerNode::insert(int loc, unsigned long min_key, BPTNode* node, bool l_r) {
	/* 内部节点不存在重复元问题，直接插入
	* key插入到loc
	* node插入到loc+1还是loc由l_r决定
	*/
	// 直接插入
	for (int i = size - 1; i >= loc; i--) {
		keys[i + 1] = keys[i];
	}
	keys[loc] = min_key;

	if (!l_r)
		loc++;
	for (int i = size; i >= loc; i--) {
		nodes[i + 1] = nodes[i];
	}
	nodes[loc] = node;
	size++;
}

bool BPTInnerNode::remove(unsigned long key) {
	/*并未使用*/
	return true;
}

void BPTInnerNode::__remove(int loc, bool l_r) {
	/*
	* loc	: 待删除的key的位置
	* l_r	: 待删除key的左还是右分支
	*/
	for (int i = loc + 1; i < size; i++) {
		keys[i - 1] = keys[i];
	}
	// 右分支
	if (!l_r) {
		loc++;
	}
	for (int i = loc + 1; i <= size; i++) {
		nodes[i - 1] = nodes[i];
	}
	size--;
	assert(size >= 0);
}

bool BPTInnerNode::concealed() {
	return concealed(size);
}

bool BPTInnerNode::concealed(int c) {
	// 分裂时最小的一边大小根据branchs奇偶性不同
	if (branchs % 2) {
		return c < branchs / 2;
	}
	return c < branchs / 2 - 1;
}

unsigned long BPTInnerNode::borrow(BPTNode* silbing, unsigned long key, bool l_r) {
	/*
	* key	: 拼接兄弟节点node使用的key
	* l_r	: 左/右兄弟
	* return: 用于父节点更新的key
	*/
	BPTInnerNode* s_node = (BPTInnerNode*)silbing;
	unsigned long ret_key;
	// 向左节点借一个元素
	if (l_r) {
		insert(0, key, s_node->nodes[s_node->size], true);
		ret_key = s_node->keys[s_node->size - 1];
		s_node->__remove(s_node->size - 1, false);
		return ret_key;
	}

	// 向右节点借一个元素
	insert(size, key, s_node->nodes[0], false);
	ret_key = s_node->keys[0];
	s_node->__remove(0, true);
	return ret_key;
}
void BPTInnerNode::append(BPTNode* node, unsigned long key) {
	/*
	* key	: 两个节点合并时，对应父节点的key
	*/
	BPTInnerNode* i_node = (BPTInnerNode*)node;
	assert(size + i_node->size < branchs);
	//assert(keys[0] < i_node->keys[0]);

	for (int i = 0; i < i_node->size; i++) {
		keys[size + 1 + i] = i_node->keys[i];
		nodes[size + 1 + i] = i_node->nodes[i];
	}
	nodes[size + 1 + i_node->size] = i_node->nodes[i_node->size];
	keys[size] = key;
	size += i_node->size + 1;
}

bool BPTInnerNode::contain(unsigned long key) {
	int loc;
	return bn_search(keys, key, size, loc);
}

char* BPTInnerNode::serialize(int& len) {
	/*序列化格式说明-按字节顺序
	* sizeof(int)			: 序列化长度
	* 1						: 标志字节
	* sizeof(int)			: size字段
	* sizeof(ulong)*size	: keys数组
	* sizeof(int)			: branchs字段
	*
	* nodes数组字段不记录，DFS序列化树和反序列化
	* 故节点在文件中位置标示了连接关系
	*/
	len = sizeof(int) * 3 + 1 + sizeof(unsigned long) * size;
	char flags = BPT_INNER_NODE;

	char* serialization = new char[len];
	char* org_serialization = serialization;
	((int*)serialization)[0] = len;
	serialization += sizeof(int);
	serialization[0] = flags;
	serialization += 1;
	((int*)serialization)[0] = size;
	serialization += sizeof(int);
	for (int i = 0; i < size; i++) {
		((unsigned long*)serialization)[i] = keys[i];
	}
	serialization += sizeof(unsigned long) * size;
	((int*)serialization)[0] = branchs;

	return org_serialization;
}

bool BPTInnerNode::load(char* serialization) {
	/*
	* 注意并没有完全检查节点序列的完整性
	* 节点数据被破坏仍有可能被序列化
	* 但最终的BPT将不正确，程序异常终止
	*/
	int len = ((int*)serialization)[0];
	if (len < 0) return false;
	serialization += sizeof(int);
	char flags = serialization[0];
	if (!(flags & BPT_INNER_NODE)) return false;
	serialization += 1;

	size = ((int*)serialization)[0];
	serialization += sizeof(int);
	for (int i = 0; i < size; i++) {
		keys[i] = ((unsigned long*)serialization)[i];
	}
	serialization += sizeof(unsigned long) * size;
	branchs = ((int*)serialization)[0];
	if (branchs < 0) return false;

	return true;
}
